8304. Веселая функция

Вычислите значение функции

Вход. Два целых числа x, y (0 ≤ x, y ≤ 50).

Выход. Выведите значение функции f(x, y).

Пример входа 1	Пример выхода 1
2 3	4
Пример входа 2	Пример выхода 2
34 12	6

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Реализуем рекурсивную функцию с запоминанием результатов.

Реализация алгоритма

Объявим двумерный массив для запоминания значений функции: dp[x][y] = f(x, y).

long long dp[51][51];

Реализация рекурсивной функции f с запоминанием.

long long f(int x, int y)

{

if (x <= 0 || y <= 0) return 0;

if (dp[x][y] != -1) return dp[x][y];

if (x <= y) return dp[x][y] = f(x - 1,y - 2) + f(x - 2,y - 1) + 2;

return dp[x][y] = f(x - 2,y - 2) + 1;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&x,&y);

Инициализируем ячейки массива dp значением -1.

memset(dp,-1,sizeof(dp));

Вызываем функцию f(x, y) и выводим ее значение.

printf("%lld\n",f(x,y));

Python реализация

Реализация рекурсивной функции f с запоминанием.

def f(x, y):

if x <= 0 or y <= 0: return 0

if dp[x][y] != -1: return dp[x][y]

if x <= y:

dp[x][y] = f(x - 1, y - 2) + f(x - 2, y - 1) + 2

else:

dp[x][y] = f(x - 2, y - 2) + 1

return dp[x][y]

Основная часть программы. Читаем входные данные.

x, y = map(int, input().split())

Объявим двумерный список для запоминания значений функции: dp[x][y] = f(x, y). Инициализируем ячейки списка значением -1.

dp = [[-1] * 51 for _ in range(51)]

Вызываем функцию f(x, y) и выводим ее значение.

print(f(x, y))